package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/'>二叉树中的伪回文路径(Pseudo-Palindromic Paths in a Binary Tree)</a>
 * <p>给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。</p>
 * <p>请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [2,3,1,3,1,null,1]
 *                  2
 *                /  \
 *               3    1
 *              / \    \
 *             3   1    1
 *      输出：2
 *      解释：上图为给定的二叉树。总径共有 3 条从根到叶子的路：[2,3,3] ，[2,1,1]，[2,3,1] 。
 *              在这些路径中，[2,3,3] 存在回文排列 [3,2,3] ，[2,1,1] 存在回文排列 [1,2,1] 。
 *
 * 示例 2：
 *      输入：root = [2,1,1,1,3,null,null,null,null,null,1]
 *                    2
 *                  /   \
 *                 1     1
 *                /\
 *               1  3
 *                   \
 *                    1
 *      输出：1
 *      解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
 *              这些路径中只有[2,1,1] 存在回文排列 [1,2,1] 。
 *
 * 示例 3：
 *      输入：root = [9]
 *      输出：1
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给定二叉树的节点数目在范围 [1, 10^5] 内</li>
 *     <li>1 <= Node.val <= 9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/30 17:06
 */
public class LC1457PseudoPalindromicPathsInBinaryTree_M {

    static class Solution {

        /**
         * <p>回文序列：</p>
         * <ul>
         *     <li>偶回文序列：对于长为偶数的路径，只要路径上的每个数字的出现次数均为偶数，就一定可以重新排列成回文序列。</li>
         *     <li>奇回文序列：对于长为奇数的路径，恰好有一个数字的出现次数为奇数，其余数字的出现次数均为偶数，就一定可以重新排列成回文序列。</li>
         * </ul>
         * 如何维护出现次数的奇偶性？==>有两种写法：数组 / 位运算。
         *
         * @param root 树的根节点
         * @return 伪回文 路径的数目
         */
        public int pseudoPalindromicPaths(TreeNode root) {
            return dfs(root, new int[10]);
        }

        private int dfs(TreeNode currNode, int[] times) {
            if (currNode == null) {
                return 0;
            }
            // 修改 node.val出现次数的奇偶性，用^1。0^1 = 1 ，1^1 =0
            times[currNode.val] ^= 1;
            int res;
            // 如果是叶子节点
            if (currNode.left == null && currNode.right == null) {
                res = getOddNumberTimes(times) <= 1 ? 1 : 0;
            } else {
                res = dfs(currNode.left, times) + dfs(currNode.right, times);
            }
            // 回溯：恢复到递归 node 之前的状态（不做这一步就把 node.val 算到其它路径中了）
            times[currNode.val] ^= 1;
            return res;
        }

        private int getOddNumberTimes(int[] times) {
            // 出现奇数次数的数字的基数
            int OddNumberTimes = 0;
            for (int time : times) {
                OddNumberTimes += time;
            }
            return OddNumberTimes;
        }
    }
}
